FFT, FMM, or Multigrid? A comparative Study of State-Of-the-Art Poisson Solvers for Uniform and Nonuniform Grids in the Unit Cube

摘要

In this work, we benchmark and discuss the performance of the scalablemethods for the Poisson problem which are used widely in practice: the fastFourier transform (FFT), the fast multipole method (FMM), the geometricmultigrid (GMG), and algebraic multigrid (AMG). In total we compare fivedifferent codes, three of which are developed in our group. Our FFT, GMG, andFMM are parallel solvers that use high-order approximation schemes for Poissonproblems with continuous forcing functions (the source or right-hand side). Weexamine and report results for weak scaling, strong scaling, and time tosolution for uniform and highly refined grids. We present results on theStampede system at the Texas Advanced Computing Center and on the Titan systemat the Oak Ridge National Laboratory. In our largest test case, we solved aproblem with 600 billion unknowns on 229,379 cores of Titan. Overall, allmethods scale quite well to these problem sizes. We have tested all of themethods with different source functions (the right-hand side in the Poissonproblem). Our results indicate that FFT is the method of choice for smoothsource functions that require uniform resolution. However, FFT loses itsperformance advantage when the source function has highly localized featureslike internal sharp layers. FMM and GMG considerably outperform FFT for thosecases. The distinction between FMM and GMG is less pronounced and is sensitiveto the quality (from a performance point of view) of the underlyingimplementations. The high-order accurate versions of GMG and FMM significantlyoutperform their low-order accurate counterparts.